# LeetCode 218. 天际线问题
#　https://leetcode.cn/problems/the-skyline-problem/description/
from typing import List
import heapq

from sortedcontainers import SortedList


class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        result = []
        sky = []
        h = 0
        for left, right, height in buildings:
            # 以右坐标划分
            while sky and sky[0][0] < left:
                r, rh = heapq.heappop(sky)
                if h == rh:
                    rh = max(sky, key=lambda x:x[1])[1] if sky else 0
                    if rh != h:
                        h = rh
                        result.append([r, h])
            # 当前height最大，把left和height加入result
            if height > h:
                h = height
                if result and result[-1][0] == left:
                    result[-1][1] = height
                else:
                    result.append([left, height])

            heapq.heappush(sky, [right, height])

        while sky:
            r, rh = heapq.heappop(sky)
            if h == rh:
                rh = max(sky, key=lambda x: x[1])[1] if sky else 0
                if rh != h:
                    h = rh
                    result.append([r, h])
        return result


from sortedcontainers import SortedList
# 事件发生
class Solution2:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        result = []
        buildings_change = []
        for left, right, height in buildings:
            buildings_change.append([left, -height])
            buildings_change.append([right, height])
        buildings_change.sort()
        # print(buildings_change)

        height_max, prev_max = 0, 0
        # heights = SortedList([0])
        heights = [0]
        for event_index, height_curr in buildings_change:
            if height_curr < 0:
                # heights.add(height_curr)
                heights.append(height_curr)
                heights.sort()
            else:
                heights.remove(-height_curr)
            height_max = -heights[0]
            if height_max != prev_max:
                result.append([event_index, height_max])
                prev_max = height_max
        return result


import heapq
# 扫描线 大根堆
class Solution3:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        result = []
        event_indics = []
        for building in buildings:
            event_indics.append(building[0])
            event_indics.append(building[1])
        event_indics.sort()
        print(event_indics)

        index = 0
        sky = []
        height_max, prev_max = 0, 0
        for event_index in event_indics:
            while index < len(buildings) and buildings[index][0] <= event_index:
                heapq.heappush(sky, (-buildings[index][2], buildings[index][1]))
                index += 1
            while sky and sky[0][1] <= event_index:
                heapq.heappop(sky)
            height_max, prev_max = - sky[0][0] if sky else 0, height_max
            if prev_max != height_max:
                result.append([event_index, height_max])

        return result


if __name__ == '__main__':
    buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
    buildings = [[0, 2, 3], [2, 5, 3]]
    # buildings = [[1,2,1],[1,2,2],[1,2,3]]   # [[1, 3], [2, 0]]
    # buildings = [[0, 3, 3], [1, 5, 3], [2, 4, 3], [3, 7, 3]]
    # buildings = [[2,14,4],[4,8,8],[6,16,4]] # [[2, 4], [4, 8], [8, 4], [16, 0]]
    # buildings = [[2,13,10],[10,17,25],[12,20,14]]   # [[2, 10], [10, 25], [17, 14], [20, 0]]
    result = Solution().getSkyline(buildings)
    print(result)
    result2 = Solution2().getSkyline(buildings)
    print(result2)
    result3 = Solution3().getSkyline(buildings)
    print(result3)
